package org.example.algorithm.dp;

public class ClimbStairsSolution {

    public static void main(String[] args) {
        ClimbStairsSolution climbStairsSolution = new ClimbStairsSolution();
        int res = climbStairsSolution.climbStairs(3);
        System.out.println(res);
    }

    public int climbStairs(int n) {
        if (n==1) {
            return 1;
        }
        if (n==2) {
            return 2;
        }
        int tempFirst = 1;
        int tempTwo = 2;
        for (int i=3;i<=n;i++) {
            int temp = tempTwo;
            tempTwo = tempTwo + tempFirst;
            tempFirst = temp;
        }
        return tempTwo;
    }

    /**
     * 使用动态规划
     */
    public int climbStairs3(int n) {
        if (n==1) {
            return 1;
        }
        if (n==2) {
            return 2;
        }
        int[] res = new int[n];
        res[0] = 1;
        res[1] = 2;
        for (int i=2;i<res.length;i++) {
            res[i] = res[i-1] + res[i-2];
        }
        return res[n-1];
    }

    /**
     * n较大时超时
     * @param n
     * @return
     */
    public int climbStairs2(int n) {
        if (n==1) {
            return 1;
        }
        if (n==2) {
            return 2;
        }
        return climbStairs(n-1) + climbStairs(n-2);
    }
}
